package _02_cirdoublyLinkedList;

public class CirDoublyLinkedList<T> {
    
    // 头结点
    public DoubleNode<T> head;
    
    // 创建空循环双链表
    public CirDoublyLinkedList() {
        
        // head的prev, next和data都是null
        this.head = new DoubleNode<T>();
        this.head.prev = this.head;
        this.head.next = this.head;
    }
    
    
    // 判空
    public boolean isEmpty() {
        return this.head.next == this.head;
    }
    
    // 构造循环双链表，由value数组提供元素，尾插入
    public CirDoublyLinkedList(T[] value) {
        this();
        DoubleNode<T> rear = this.head;
        for (int i = 0; i < value.length; i++) {
            // 以第一个结点为例：head <--> a0 --> head; 以第二个结点为例：head <--> a0 <--> a1 --> head
            rear.next = new DoubleNode<T>(value[i], rear, this.head);
            rear = rear.next;
        }
        this.head.prev = rear;
    }
    
    // 深拷贝
    public CirDoublyLinkedList(CirDoublyLinkedList<T> cd) {
        this();
        DoubleNode<T> rear = this.head;
        for (DoubleNode<T> p = cd.head.next; p != cd.head; p = p.next) {
            // head <--> a0 --> head; head <--> a0 <--> a1 --> head
            rear.next = new DoubleNode(p.data, rear, this.head);
            rear = rear.next;
        }
        this.head.prev = rear;
    }
    
    // 返回链表的长度
    public int size() {
        int count = 0;
        for (DoubleNode<T> p = this.head.next; p != head; p = p.next) {
            count++;
        }
        return count;
    }

    // 返回第i个元素，0≤i<长度。若i越界，返回null。
    public T get(int i) {
        DoubleNode<T> p = this.head;
        for (int j = 0; j < i; j++) {
            p = p.next;
        }
        return i >= 0 && i < this.size() ? p.next.data : null;
    }
    
    // 返回链表中每个元素的字符串描述
    public String toString() {
        if (this.isEmpty()) {
            return null;
        }
        DoubleNode<T> p = this.head.next;
        String str = "{";
        while (p.next != this.head) {
            str += p.data.toString() + ", ";
            p = p.next;
        }
        return str + p.data + "}";
    }
    
    // 尾插入x元素，返回x结点。算法在头结点之前插入
    public DoubleNode<T> insert(int i, T x) {
        if (x == null) {
            throw new NullPointerException("x==null");
        }
        DoubleNode<T> p = this.head;
        for (int j = 0; j < i; j++) {
            p = p.next;
        }
        // 以头插入为例：head <--> head.next ==> head <-- node --> head.next; head <--> head.next
        DoubleNode<T> node = new DoubleNode(x, p, p.next);
        // 设置完node的前驱和后继，还得为node的前驱的后继设置为node，为node的后继的前驱设置为node
        // 也是以头插入为例：head --> node
        p.next = node;
        // 也是以头插入为例：node <-- head.next
        p.next.prev = node;
        return node;
    }
    
    // 设置第i个元素为x，0≤i<长度。若i越界，抛出序号越界异常；若x==null，抛出空对象异常。
    public void set(int i, T x) {
        if (x == null) {
            throw new NullPointerException("x==null");
        }
        DoubleNode<T> p = this.head.next;
        for (int j = 0; j < i; j++) {
            p = p.next;
        }
        if (i >= 0 && p != null) {
            p.data = x;
        } else {
            throw new IndexOutOfBoundsException(i+"");
        }
    }
    
    // 顺序查找首次出现的与key相等元素，返回结点，若查找不成功返回null。算法同单链表
    public DoubleNode<T> search(T key) {
        for (DoubleNode<T> p = this.head.next; p != head; p = p.next) {
            if (p.data.equals(key)) {
                return p;
            }
        }
        return null;
    }
    // 删除首个与key相等元素结点，返回被删除元素，查找不成功返回null。
    // 以头删除为例：head <--> p <--> p.next ==> head <--> p.next
    public T remove(T key) {
        DoubleNode<T> p = search(key);
        if (p != null) {
            p.prev.next = p.next;
            p.next.prev = p.prev;
            return p.data;
        }
        return null;
    }
    
    // 比较两条循环双链表是否相等，覆盖Object类的equals(obj)方法。
    public boolean equals(Object obj) {
        if (this == obj) {
            return true;
        }
        if (!(obj instanceof CirDoublyLinkedList<?>)) {
            return false;
        }
        DoubleNode<T> p = this.head.next;
        CirDoublyLinkedList<T> that = (CirDoublyLinkedList<T>)obj;
        DoubleNode<T> q = that.head.next;
        while (p != head && q != head && p.equals(q)) {
            p = p.next;
            q = p.next;
        }
        return p == head && q == head;
    }
    
    // 反转循环双链表（不会写）
    // head <-> head.next(a0) <-> head.next.next(a1) <-> head.next.next.next(a2) <->
    // a0 <-> head <-> a0
    // a1 <-> a0 <-> head <-> a1
    // a2 <-> a1 <-> a0 <-> head <-> a2
    public static <T> void reverse(CirDoublyLinkedList<T> cd) {
        DoubleNode<T> p = cd.head.next, front = cd.head;
        while (p != cd.head) {
            DoubleNode<T> succ = p.next;
            p.next = front;
            front.prev = p;
            front = p;
            p = succ;
            System.out.println(front.data.toString());
        }
        cd.head.prev = p;
    }
    
    // 倒叙返回每个元素的字符串描述
    public String reverseToString() {
        String str = "{";
        DoubleNode<T> p = null;
        for (p = this.head.prev; p.prev != this.head; p = p.prev) {
            str += p.toString() + ", ";
        }
        return str + p.toString() + "}";
    }
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Integer[] nums1 = {};
        CirDoublyLinkedList<Integer> cd1 = new CirDoublyLinkedList<Integer>(nums1);
        Integer[] nums2 = {0, 1, 2, 3, 4, 5};
        CirDoublyLinkedList<Integer> cd2 = new CirDoublyLinkedList<Integer>(nums2);
        
        
        System.out.println("测试元素的prev是指向前驱还是head");
        System.out.print(cd2.head.next.next.prev.equals(cd2.head) + ", ");
        System.out.print(cd2.head.next.next.prev.toString() + ", ");
        System.out.println(cd2.head.next.next.next.prev.toString());
        
        System.out.println("测试isEmpty方法：");
        System.out.println(cd1.isEmpty() + ", " + cd2.isEmpty());
        
        System.out.println("测试size方法：");
        System.out.println(cd1.size() + ", " + cd2.size());
        
        System.out.println("测试get和toString方法：");
        System.out.println(cd2.get(3) + ", " + cd1.toString() + ", " + cd2.toString());
        
        System.out.println("测试set方法：");
        cd2.set(2, 888);
        System.out.println(cd2.toString());
        
        System.out.println("测试insert方法：");
        System.out.println(cd2.insert(7, 555) + ", " + cd2.toString());
        
        System.out.println("测试search和remove方法：");
        System.out.println(cd2.remove(3));
        System.out.println(cd2.toString());
        
        System.out.println("测试equals方法：");
        System.out.println(cd2.equals(cd2) + ", " + cd1.equals(cd2));
        
        System.out.println("测试深拷贝构造方法：");
        CirDoublyLinkedList<Integer> cd3 = new CirDoublyLinkedList<Integer>(cd2);
        System.out.println(cd3.toString());
        
        System.out.println("测试reverse和reverseToString方法：");
        System.out.println(cd3.reverseToString());
        reverse(cd3);
        System.out.println(cd3.toString());
    }
}
